package com.leetBook.Krahets.linkedList;

import org.junit.Test;

import java.util.HashMap;

/**
 * 《图解算法与数据结构》链表第 5 题：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *  与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
 */
public class CopyRandomList {
    /**
     * 官方解法，考虑构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点
     * @param head 头结点
     * @return 复制之后的头节点
     */
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != null) {
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        // 3. 拆分两链表
        cur = head.next;
        Node pre = head, res = head.next;
        while(cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }

    @Test
    public void fun1(){
        Node node0 = new Node(0);
        Node node = new Node(7,
                    new Node(13,
                            new Node(11,
                                    new Node(10,
                                            new Node(1, null, node0), new Node(2)), new Node(4)), node0), null);
        System.out.println(node);

        Node node1 = copyRandomList(node);
        System.out.println(node1);
    }

//    public Node copyRandomList(Node head) {
//        if (head == null){
//            return null;
//        }
//
//        HashMap<Integer, Node> map = new HashMap<>();
//
//        Node tmp = new Node(head.val);
//        Node node = tmp;
//        map.put(tmp.val, tmp);
//        while (head != null){
//            tmp.random = extracted(head.random, map);
//
//            tmp.next = extracted(head.next, map);
//
//            tmp = tmp.next;
//            head = head.next;
//        }
//
//        return node;
//    }
//
//    /**
//     * 复制节点
//     * @param src 源节点
//     * @param map 节点集合
//     * @return Node 目标节点
//     */
//    private Node extracted(Node src, HashMap<Integer, Node> map) {
//        if (src != null){
//            int val = src.val;
//            Node node1 = map.get(val);
//            if (node1 == null){
//                Node node2 = new Node(val);
//
//                map.put(val, node2);
//                return node2;
//            }else {
//                return node1;
//            }
//        }
//
//        return null;
//    }
}



class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }

    public Node(int val, Node next, Node random) {
        this.val = val;
        this.next = next;
        this.random = random;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", next=" + next +
                ", random=" + random +
                '}';
    }
}